package exercises.leetcode;

import java.util.Arrays;

/**
 * <a href="https://leetcode-cn.com/problems/delete-operation-for-two-strings/">
 * 583. 两个字符串的删除操作</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
 * <p>
 * 示例：
 * <p>
 * 输入: "sea", "eat"
 * 输出: 2
 * 解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
 *  
 * <p>
 * 提示：
 * <li>给定单词的长度不超过500。</li>
 * <li>给定单词中的字符只含有小写字母。</li>
 *
 * @author or2
 * @date 2021年09月25日 时间: 9:58
 */
public class No853 {
    public int minDistance(String word1, String word2) {
        char[] w1 = word1.toCharArray();
        char[] w2 = word2.toCharArray();
        int length1 = w1.length;
        int length2 = w2.length;

        /*dp初始化*/
        short[][] dp = new short[length1][length2];
        for (int i = 0; i < length2; i++) {
            if (w1[0] == w2[i]) {
                Arrays.fill(dp[0], i, length2, (short) 1);
                break;
            }
        }
        for (int i = 0; i < length1; i++) {
            if (w2[0] == w1[i]) {
                for (int j = i; j < length1; j++)
                    dp[j][0] = 1;
                break;
            }
        }
        /*递推求解*/
        for (int i = 1; i < length1; i++) {
            for (int j = 1; j < length2; j++) {
                if (w1[i] == w2[j])
                    dp[i][j] = (short) (1 + dp[i - 1][j - 1]);
                else
                    dp[i][j] = (short) Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        /*总长度 - 最长子序列长度得出需要删减的字符数目*/
        short max = dp[length1 - 1][length2 - 1];
        return length1 - max + length2 - max;
    }

    /**
     * 空间进行优化 - dp数组由二维变一维
     *
     * @param word1 字符串①
     * @param word2 字符串②
     * @return 最少删除的字符数
     */
    public int optimize(String word1, String word2) {
        char[] w1 = word1.toCharArray();
        char[] w2 = word2.toCharArray();
        /*为节省dp空间, 使第一个数组为较短的一个*/
        if (w1.length > w2.length) {
            char[] temp = w1;
            w1 = w2;
            w2 = temp;
        }
        int length1 = w1.length;

        /*dp数组初始化 - 冗余一个位置, 避免边界检查(类似于链表头结点)*/
        short[] dp = new short[length1 + 1];
        for (int i = 1; i <= length1; i++) {
            if (w1[i - 1] == w2[0]) {
                Arrays.fill(dp, i, length1 + 1, (short) 1);
                break;
            }
        }

        /*递推dp*/
        int length2 = w2.length;
        for (int i = 1; i < length2; i++) {
            /*获取上一次的信息*/
            short[] oldDp = dp.clone();
            for (int j = 1; j <= length1; j++) {
                if (w1[j - 1] == w2[i]) {
                    dp[j] = (short) (oldDp[j - 1] + 1);
                } else {
                    dp[j] = (short) Math.max(dp[j], dp[j - 1]);
                }
            }
        }

        short max = dp[length1];
        return length1 - max + length2 - max;
    }


    /**
     * 空间进行优化 - dp数组由二维变一维
     *
     * @param word1 字符串①
     * @param word2 字符串②
     * @return 最少删除的字符数
     */
    public int optimizest(String word1, String word2) {
        char[] w1 = word1.toCharArray();
        char[] w2 = word2.toCharArray();
        /*为节省dp空间, 使第一个数组为较短的一个*/
        if (w1.length > w2.length) {
            char[] temp = w1;
            w1 = w2;
            w2 = temp;
        }
        int length1 = w1.length;

        /*dp数组初始化 - 冗余一个位置, 避免边界检查(类似于链表头结点)*/
        short[] dp = new short[length1 + 1];
        for (int i = 1; i <= length1; i++) {
            if (w1[i - 1] == w2[0]) {
                Arrays.fill(dp, i, length1 + 1, (short) 1);
                break;
            }
        }

        /*递推dp*/
        int length2 = w2.length;
        for (int i = 1; i < length2; i++) {
            /*使用单个常量记录旧值*/
            for (int j = 1, pre = 0; j <= length1; j++) {
                int old = dp[j];
                if (w1[j - 1] == w2[i]) {
                    dp[j] = (short) (pre + 1);
                } else {
                    dp[j] = (short) Math.max(dp[j], dp[j - 1]);
                }
                pre = old;
            }
        }

        short max = dp[length1];
        return length1 - max + length2 - max;
    }
}
